package com.mystudy.leetcode.problem.link.p_82;

import com.mystudy.leetcode.base.ListNode;
import com.mystudy.leetcode.base.ListNodeUtils;
import org.junit.Test;

import java.util.HashSet;

/**
 * @program: infoalgorithm
 * @description: 中等问题:删除排序链表中的重复元素2
 * @author: zhouzhilong
 * @create: 2019-07-08 15:55
 **/
public class Solution {



    @Test
    public void test(){
        ListNode listNode = ListNodeUtils.generateLinkList(new int[]{1, 2, 3, 3, 4, 4, 5});
        ListNode listNode1 = deleteDuplicates(listNode);
        ListNodeUtils.show(listNode1);
    }





    /**
     * 死办法,效率低考虑替代方法
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        ListNode cur = head;

        HashSet<Integer> listNodes = new HashSet<>();
        HashSet<Integer> visted =  new HashSet<>();
        while (cur != null) {
            if(listNodes.contains(cur.val)){
                visted.add(cur.val);
            }else{
                listNodes.add(cur.val);
            }
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            if (visted.contains(cur.val)) {
                ListNode nextTemp = cur.next;
                prev.next = nextTemp;
                cur = nextTemp;
            } else {
                cur = cur.next;
                prev = prev.next;
            }
        }

        return dummyHead.next;

    }
}
